1. Field of the Invention
The invention relates to a method and apparatus for high performance switching in local area communications networks such as token ring, ATM, ethernet, fast ethernet, and gigabit ethernet environments, generally known as LANs. In particular, the invention relates to a new switching architecture in an integrated, modular, single chip solution, which can be implemented on a semiconductor substrate such as a silicon chip.
2. Description of the Related Art
As computer performance has increased in recent years, the demands on computer networks has significantly increased; faster computer processors and higher memory capabilities need networks with high bandwidth capabilities to enable high speed transfer of significant amounts of data. The well-known ethernet technology, which is based upon numerous IEEE ethernet standards, is one example of computer networking technology which has been able to be modified and improved to remain a viable computing technology. A more complete discussion of prior art networking systems can be found, for example, in SWITCHED AND FAST ETHERNET, by Breyer and Riley (Ziff-Davis, 1996), and numerous IEEE publications relating to IEEE 802 standards. Based upon the Open Systems Interconnect (OSI) 7-layer reference model, network capabilities have grown through the development of repeaters, bridges, routers, and, more recently, xe2x80x9cswitchesxe2x80x9d, which operate with various types of communication media. Thickwire, thinwire, twisted pair, and optical fiber are examples of media which has been used for computer networks. Switches, as they relate to computer networking and to ethernet, are hardware-based devices which control the flow of data packets or cells based upon destination address information which is available in each packet. A properly designed and implemented switch should be capable of receiving a packet and switching the packet to an appropriate output port at what is referred to wirespeed or linespeed, which is the maximum speed capability of the particular network. Basic ethernet wirespeed is up to 10 megabits per second, and Fast Ethernet is up to 100 megabits per second. The newest ethernet is referred to as gigabit ethernet, and is capable of transmitting data over a network at a rate of up to 1,000 megabits per second. As speed has increased, design constraints and design requirements have become more and more complex with respect to following appropriate design and protocol rules and providing a low cost, commercially viable solution. For example, high speed switching requires high speed memory to provide appropriate buffering of packet data; conventional Dynamic Random Access Memory (DRAM) is relatively slow, and requires hardware-driven refresh. The speed of DRAMs, therefore, as buffer memory in network switching, results in valuable time being lost, and it becomes almost impossible to operate the switch or the network at linespeed. Furthermore, external CPU involvement should be avoided, since CPU involvement also makes it almost impossible to operate the switch at linespeed. Additionally, as network switches have become more and more complicated with respect to requiring rules tables and memory control, a complex multi-chip solution is necessary which requires logic circuitry, sometimes referred to as glue logic circuitry, to enable the various chips to communicate with each other. Additionally, cost/benefit tradeoffs are necessary with respect to expensive but fast SRAMs versus inexpensive but slow DRAMs. Additionally, DRAMs, by virtue of their dynamic nature, require refreshing of the memory contents in order to prevent losses thereof. SRAMs do not suffer from the refresh requirement, and have reduced operational overhead which compared to DRAMs such as elimination of page misses, etc. Although DRAMs have adequate speed when accessing locations on the same page, speed is reduced when other pages must be accessed.
Referring to the OSI 7-layer reference model discussed previously, and illustrated in FIG. 7, the higher layers typically have more information. Various types of products are available for performing switching-related functions at various levels of the OSI model. Hubs or repeaters operate at layer one, and essentially copy and xe2x80x9cbroadcastxe2x80x9d incoming data to a plurality of spokes of the hub. Layer two switching-related devices are typically referred to as multiport bridges, and are capable of bridging two separate networks. Bridges can build a table of forwarding rules based upon which MAC (media access controller) addresses exist on which ports of the bridge, and pass packets which are destined for an address which is located on an opposite side of the bridge. Bridges typically utilize what is known as the xe2x80x9cspanning treexe2x80x9d algorithm to eliminate potential data loops; a data loop is a situation wherein a packet endlessly loops in a network looking for a particular address. The spanning tree algorithm defines a protocol for preventing data loops. Layer three switches, sometimes referred to as routers, can forward packets based upon the destination network address. Layer three switches are capable of learning addresses and maintaining tables thereof which correspond to port mappings. Processing speed for layer three switches can be improved by utilizing specialized high performance hardware, and off loading the host CPU so that instruction decisions do not delay packet forwarding.
The present invention is directed to a switch-on-chip solution for a network switch, capable of use at least on ethernet, fast ethernet, and gigabit ethernet systems, wherein all of the switching hardware is disposed on a single microchip. The present invention is configured to maximize the ability of packet-forwarding at linespeed, and to also provide a modular configuration wherein a plurality of separate modules are configured on a common chip, and wherein individual design changes to particular modules do not affect the relationship of that particular module to other modules in the system.
The present invention, therefore, is related to a switch on chip architecture which utilizes a novel memory access protocol and memory configuration which can minimize manufacturing costs, and maximize performance. The invention is also directed to a method of packet switching.
The invention is therefore directed to a network switch for network communications, with the data switch including at least one first data port interface. The data port interface supports a plurality of data ports which transmit and receive data at a first data rate. At least one second data port interface is provided; the at least one second data port interface supports a plurality of data ports transmitting and receiving data at a second data rate. A CPU interface is provided, with the CPU interface configured to communicate with a CPU. An internal memory is provided, and communicates with the at least one first data port interface and the at least one second data port interface. A memory management unit is provided, and includes an external memory interface for communicating data with at least one of the first data port interface and the second data port interface and an external memory. A communication channel is provided, with the communication channel communicating data and messaging information between the at least one first data port interface, the at least one second data port interface, the internal memory, and the memory management unit. The memory management unit directs data from one of the first data port and the second data port to one of the internal memory and the external memory interface, according to a predetermined algorithm.
The invention may include, in the first data port interface, a packet slicing unit for slicing variable length packets into a plurality of equal length cells. The packet slicing unit includes a padding unit for including padding bits into a last cell of the plurality of equal length cells if the last cell does not include a sufficient number of bits to match a length of the equal length cells.
The data switch may also be such that the communication channel includes three separate communication channels, with the three communication channels including a first channel for communicating cell data between the plurality of data ports in the first data port interface, the plurality of data ports in the second data port interface, the internal memory, and the external memory interface, and a second channel, synchronously locked with the first channel, for communicating message information corresponding to the cell data on the first channel, and a third channel, independent from the first and second channel, for communicating sideband message information.
The network switch can, in a preferred embodiment, be integrated on a single ASIC chip.
The invention is also directed to a method of switching packets in a communications network. The method includes the steps of receiving an incoming data packet on a first data port, then slicing the data packet into a plurality of equal length cells. A packet length is estimated, based upon an incoming cell count and egress information. It is then determined whether an external memory is empty, and if the external memory is empty, it is then determined whether the estimated cell count is greater than an admission low watermark for an internal memory. The plurality of equal length cells representing the packet is admitted into the internal memory if the estimated cell count is below the admission low watermark. If the estimated cell count is above the admission high watermark, the cell is sent to the external memory. If the estimated cell count is above the low watermark but below the high watermark, a determination is performed to determine whether to admit the data into internal memory or external memory. If sufficient internal memory is available, the cells representing the packet are admitted into the internal memory.
If it is determined that the number of cells in the global buffer memory pool (GBP) is not zero, then the method includes the steps of determining whether the estimated cell count is below an admission high watermark for the internal memory. If the estimated cell count is above the admission high watermark, it is then determined whether the estimated cell count is below an external memory admission low watermark. If so, it is then determined whether or not a cell count of the cells in the external memory is less than or equal to a reroute limit value. If the external memory cell count is less than or equal to the reroute limit value, then a step is performed of adding the estimated cell count to the external memory cell count, and then determining whether a sum of these counts is less than an estimated cell count low watermark. If so, the plurality of equal length cells representing the packet is admitted to the internal memory, and if not, the plurality of equal length cells representing the packet is admitted to the external memory. If it is determined that the estimated cell count is less than the admission high watermark, the plurality of equal length cells representing the packet is admitted to the external memory. If it is determined that the estimated cell count is less than the external memory admission low watermark, the plurality of equal length cells representing the packet is admitted to the external memory. If the cell count of the external memory is determined to be greater than the reroute limit value, the plurality of equal length cells representing the packet is admitted to the external memory. In other words, cells are admitted into internal memory if there is sufficient dynamic space available. Dynamic space is defined as the difference in space between the sum of the admission high watermark and the sum of the low watermarks; this dynamic space is available for any port to utilize, until such time as there is no more dynamic space available.